package a00_LeetCode.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author quan
 * @Description 对称二叉树
 * 给你一个二叉树的根节点 root,检查它是否轴对称。
 * @Date 2023/3/25 10:32
 */
public class Num101_isSymmetric {
    /** 方法1： 迭代法
     * 目的：传入一棵树的根，可以知道该树是不是轴对称的
     */
    /*public boolean isSymmetric(TreeNode root) {
        //判断是否有根:没有根存在或者整棵树只有一个根存在，则为true
        if(root==null || root.left==null&&root.right==null){
            return true;
        }
        //走到这说明有根存在:判断根的左右结构是否相同
        return isMirror(root.left,root.right);
    }
    *//**
     * 目的：传入一棵树的左右节点，可以判断该树是不是镜像相等:是不是轴对称的树
     *//*
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        //(1)处理树根到的情况
        //判断两个树是否为空
        if(t1==null &&t2==null){
            return true;
        }
        //两个树有一个为空
        if(t1==null || t2==null){
            return false;
        }
        //两个树都不为空，则判断值是否相等
        if(t1.val != t2.val){
            return false;
        }
        //(2)判断树根的左右子树
        //t1的左孩子与t2的右孩子镜像相等，t1的右孩子与t2的左孩子镜像相等
        return isMirror(t1.left, t2.right) && isMirror(t1.right,t2.left);
    }*/

    /**
     * 方法2：迭代法：使用普通队列
     */
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()){
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if(leftNode == null && rightNode == null){
                continue;//写成return true会报错！！但是递归方式要写成return true。
            }
            if(leftNode == null && rightNode != null){
                return false;
            }
            if(leftNode != null && rightNode==null){
                return false;
            }
            if(leftNode.val != rightNode.val){
                return false;
            }
            //说明此时有左右节点且值相等:注意这里的顺序！！
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }
}
